#include<iostream>
#include<vector>
using namespace std;
int MoreThanHalfNum_Solution(vector<int>& numbers) {
    // write code here
    int n = numbers[0];
    int n_size = 1;
    for (int i = 1; i < numbers.size(); i++) {
        if (n_size == 0) {
            n = numbers[i];
            n_size++;
            continue;
        }
        if (numbers[i] == n) {
            n_size++;
        }
        else
            n_size--;
    }
    return n;
}
int main()
{
    vector<int> arr = { 1,1,1,1,1,1,2,2,2 };
    cout << MoreThanHalfNum_Solution(arr);
	return 0;
}